/**
 * 邻节点个数1的节点为叶子节点，
 * 每次删去所有叶子节点，最后剩下的一个或两个节点就是要的结果
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
export var findMinHeightTrees = function (n, edges) {
  // adj number[][] 用于记录每个节点有哪些相邻节点
  const adj = []
  // ind number[] 用于记录每个节点的相邻节点数
  const ind = []
  // 初始化 adj 和 ind
  for (let i = 0; i < n; i++) {
    adj.push([])
    ind.push(0)
  }
  for (const edge of edges) {
    adj[edge[0]].push(edge[1])
    adj[edge[1]].push(edge[0])
    ind[edge[0]]++
    ind[edge[1]]++
  }

  let queue = []
  // 把ind为1的节点，即叶子节点加入到队列中
  for (const i in ind) {
    if (ind[i] === 1) {
      queue.push(i)
    }
  }
  // 处理队列
  while (queue.length) {
    let nextQueue = []
    for (const nodeName of queue) {
      for (const nearNode of adj[nodeName]) {
        ind[nearNode]--
        if (ind[nearNode] === 1) {
          nextQueue.push(nearNode)
        }
      }
    }
    if (nextQueue.length === 0) {
      return queue
    }
    queue = nextQueue
  }
  return [0]
}
